#include "main/utils.h"
using namespace std;

int merge(vector<int> &vec, int begin, int mid, int end) {
  vector<int> vec_tmp(vec);
  int ret = 0;
  int k = end;
  int i = mid;
  int j = end;
  while (i >= begin && j > mid) {
    if (vec[i] > vec[j]) {
      ret += (j - mid);
      vec_tmp[k--] = vec[i--];
    } else {
      vec_tmp[k--] = vec[j--];
    }
  }
  while (i >= begin) {
    vec_tmp[k--] = vec[i--];
  }
  while (j > mid) {
    vec_tmp[k--] = vec[j--];
  }
  vec = vec_tmp;
  return ret;
}

int reversePairs(vector<int> &vec, int begin, int end) {
  if (begin == end)
    return 0;
  int mid = begin + ((end - begin) >> 1);
  int ret = reversePairs(vec, begin, mid) + reversePairs(vec, mid + 1, end) + merge(vec, begin, mid, end);
  return ret;
}

int main() {
  vector<int> vec = {7, 5, 6, 4};
  int ret = reversePairs(vec, 0, 3);
  cout << "The number of reverse pairs is: " << ret << endl;

  return 0;
}
